/**
 * Copyright (c) 2010 Simple Graph Tools contributors. All rights reserved.
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 * 
 *   http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *
 * $Id$
 */
package org.sgt.coredef.util;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

import org.sgt.coredef.Chain;
import org.sgt.coredef.CoredefFactory;
import org.sgt.coredef.Edge;
import org.sgt.coredef.Graph;
import org.sgt.coredef.Node;

/**
 * The graphWalker is maintaining a map of possible Chains for a given Route in
 * a Graph. It is able to explore the Graph in order to build a new Route-Chains
 * map. It is making use of a {@link IGraphWalkerPolicy} policy to get the rules
 * governing chains building. <BR/>
 * The walker handles Chains in an abstracted manner (Chains are abstract
 * EObjects in coredef model), the policy knows their concrete implementations
 * and specific handling rules. <BR/>
 * <BR/>
 * Sample usage : computes all possible chains starting on startNode and ending
 * on endNode in the given graph according to a defined walkerPolicy.<BR/>
 * <BR/>
 * <code>
 		//A graph object : graph<BR/>
 		//An associated graphWalker policy : walkerPolicy<BR/>
        //A starting and ending node : startNode endNode<BR/>
		<BR/>
		GraphWalker walker = new GraphWalker(graph);<BR/>
		// Setting walker's policy...<BR/>
		walker.setPolicy(walkerPolicy);<BR/>
		Route route = new Route(startNode, endNode);<BR/>
		walker.updateChains(route);<BR/>
		Set&lt;Chain&gt; routeChains = walker.getChains(route);<BR/>
 * </code>
 * 
 * @author Anne BUTTIGHOFFER
 * 
 */
public class GraphWalker {

	/**
	 * Our Walker's graph.
	 */
	private Graph graph;

	/**
	 * Our Walker's policy.
	 * 
	 * @see IGraphWalkerPolocy
	 */
	private IGraphWalkerPolicy policy;

	/**
	 * Our Chains map by routes.
	 */
	private Map<Route, Set<Chain>> routes2ChainsMap
		= new HashMap<Route, Set<Chain>>();

	/**
	 * Constructor.
	 * 
	 * @param newGraph
	 *            {@link Graph} the graph to walk through.
	 */
	public GraphWalker(final Graph newGraph) {
		graph = newGraph;
	}

	/**
	 * @return {@link #routes2ChainsMap}.
	 */
	public final Map<Route, Set<Chain>> getRoutes2ChainsMap() {
		return routes2ChainsMap;
	}

	/**
	 * Returns the set of chains for the given route (as stored in
	 * {@link #routes2ChainsMap}).
	 * 
	 * @param route
	 *            {@link Route}.
	 * @return the stored set of chains (may be null or empty).
	 */
	public final Set<Chain> getChains(final Route route) {
		return routes2ChainsMap.get(route);
	}

	/**
	 * @return our walker's {@link IGraphWalkerPolicy}.
	 */
	public final IGraphWalkerPolicy getPolicy() {
		return policy;
	}

	/**
	 * Sets the Walker's policy. <BR/>
	 * <EM>Setting the Policy will clear all existing chainsMap.</EM>
	 * 
	 * @param newPolicy
	 *            {@link IGraphWalkerPolicy}.
	 */
	public final void setPolicy(final IGraphWalkerPolicy newPolicy) {
		if (newPolicy != this.policy) {
			routes2ChainsMap.clear();
			this.policy = newPolicy;
		}
	}

	/**
	 * @return the {@link Graph} handled by this Walker.
	 */
	public final Graph getGraph() {
		return graph;
	}

	/**
	 * Builds the Chains starting from given route's source and ending on
	 * route's destination. The {@link #routes2ChainsMap} is updated
	 * accordingly.
	 * 
	 * @param route
	 *            {@link Route}.
	 */
	public final void updateChains(final Route route) {
		if (policy == null) {
			Logger.log("Can not update chains : null GraphWalkerPolicy");
			return;
		}
		if (graph == null || route == null || route.getSource() == null
				|| route.getDestination() == null
				|| !graph.getNodes().contains(route.getDestination())
				|| !graph.getNodes().contains(route.getSource())) {
			return;
		}
		// marking this route as explored...
		routes2ChainsMap.put(route, new HashSet<Chain>());

		Chain chain = policy.createNewChain(route, graph);
		if (chain == null) {
			return;
		}
		Set<Chain> candidates = new HashSet<Chain>();
		Set<Chain> toExplore = new HashSet<Chain>();
		Set<Chain> buffer = new HashSet<Chain>();

		toExplore.add(chain);
		buffer.addAll(toExplore);
		while (!toExplore.isEmpty()) {
			candidates.clear();
			for (Chain toGrow : toExplore) {
				// one step forward
				Set<Chain> growns = policy.growForward(toGrow, graph);
				if (growns.isEmpty()) {
					Logger.log(" ... is fully grown ...");
				}
				candidates.addAll(growns);
				buffer.remove(toGrow);
			}
			toExplore.clear();
			toExplore.addAll(candidates);
			Set<Chain> explored = new HashSet<Chain>();
			for (Chain candidate : candidates) {
				Node finalNode = ChainHelper.getLastListedNode(candidate);
				if (finalNode == null) {
					Logger.logError("Null final node in chain :" + chain);
				}
				if (!policy.canGrowForward(candidate, graph)) {
					// Check if we reached our final destination...
					Set<Edge> edges = new HashSet<Edge>(candidate.getEdges());
					Edge finalEdge = null;
					for (Edge edge : edges) {
						if (edge.getSource() == finalNode
								&& edge.getDestination() == candidate
										.getEndNode()) {
							finalEdge = edge;
							break;
						}
					}
					if (finalEdge != null) {
						// We have a good chain to store...
						Route myRoute = new Route(candidate.getStartNode(),
								candidate.getEndNode());
						Set<Chain> myChains = routes2ChainsMap.get(myRoute);
						if (myChains == null) {
							myChains = new HashSet<Chain>();
						}
						myChains.add(candidate);
						routes2ChainsMap.put(myRoute, myChains);
						Logger.log("Added chain "
								+ policy.prettyPrint(candidate));
					}
					explored.add(candidate);
				}
			}
			toExplore.removeAll(explored);
		}
	}

	/**
	 * Creates an new Chain instance with given Route set.
	 * 
	 * @param route
	 *            {@link Route}.
	 * @return the created chain (may be null if creation failed).
	 */
	public static final Chain createNewChain(final Route route) {
		if (route == null || route.getSource() == null
				|| route.getDestination() == null) {
			return null;
		}
		Chain chain = CoredefFactory.eINSTANCE.createChain();
		chain.setStartNode(route.getSource());
		chain.setEndNode(route.getDestination());
		return chain;
	}

}
